package top.likeqc.leetcode.editor.cn;

public class LinkedListCycle{
    public static void main(String[] args) {
        Solution solution = new LinkedListCycle().new Solution();
    }
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
    public class Solution {
        public boolean hasCycle(ListNode head) {
            // 双指针，p2 每次比 p1 多走一步，若存在环路，那么 p2 最终会套圈 p1
            ListNode p1, p2;
            p1 = p2 = head;
            while(p2 != null) {
                p2 = p2.next;
                if (p2 == null) {
                    break;
                }
                p1 = p1.next;
                p2 = p2.next;
                if (p1 == p2) {
                    return true;
                }
            }
            
            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
    
    class ListNode {
        int val;
        ListNode next;
        
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}